/*
给定一个元素值都大于零的整数集合，编写函数，计算如下条件的一个最大子集。
1.子集中元素互不相等。
2.子集中任意两个元素大者除以小者的余数为0.
思路：二进制集合+符合两个条件的集合存下来
*/
#include<stdio.h>
#include<stdlib.h>
#include<set>
using namespace std;
#define maxsize 10
void f(int a[],int n)
{
	for(int i=0;i<n-1;i++)   //冒泡，升序排序
		for(int j=0;j<n-1-i;j++)//n-1-(i//已经排好序的元素数
			if(a[j]>a[j+1])
			{
				int temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
	int max=0;
	int maxson[maxsize];
	for(int i=0;i<(1<<n);i++)//对i 循环，目的让 1-n 位从000 .. 000 到 111...111，取值范围
	{
		int count=0;
		int b[maxsize];//记录最大子集的元素
		for(int j=0;j<n;j++)
		{
			if(i&(1<<j))//i和1<<j 进行按位与操作时，i的第j+1个位置是1就返回1<<j（判断语句中即为true），i的第j+1个位置是0就返回0
			{
				b[count++]=a[j];  //选中a[j]
			}
		}
	    if(count>max)
		{
			int flag=1;
			for(int j=1;j<count;j++)
			{
				if(b[j]%b[j-1]!=0)//判断是否满足倍数条件
				{
					flag=0;
					break;
				}
			}
			for(int j=1;j<count;j++)//判断元素互不相等。因为数组是升序排序的，只需要比较相邻元素即可判断是否有相同元素
				if(b[j]==b[j-1])
				{
					flag=0;
					break;
				}
			if(flag==1)//满足条件，存子集
			{
				for(int j=0;j<count;j++)
					maxson[j]=b[j];
				max=count;
			}
		}
	}
	printf("{");
	int flag=1;
	for(int i=0;i<max;i++)
		if(flag==1)
		{
			printf("%d",maxson[i]);
			flag=0;
		}
		else
			printf(",%d",maxson[i]);
	printf("}");
}
int main(){
	// set<int> s={1,2,3,4,5};
	int a[6]={2,3,4,5,6,8};
	f(a,6);
	return 0;
}